from collections import deque


class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


def f(root: TreeNode):
    if not root:
        return
    print(root.val, end=" ")
    f(root.left)
    f(root.right)


def serial_by_pre(root: TreeNode):
    if not root:
        return "#_"
    res = str(root.val) + "_"
    res += serial_by_pre(root.left)
    res += serial_by_pre(root.right)
    return res


def reconstruct_by_pre(s: str):
    s = s.split("_")
    queue = deque()
    for i in s:
        queue.append(i)

    return r_b_p(queue)


def r_b_p(queue):
    tmp = queue.popleft()
    if tmp == "#":
        return None
    node = TreeNode(tmp)
    node.left = r_b_p(queue)
    node.right = r_b_p(queue)

    return node


def serial_by_lever(root: TreeNode):
    queue = deque()
    queue.append(root)
    res = str(root.val)
    while queue:
        node = queue.popleft()
        if node.left:
            queue.append(node.left)
            res += str(node.left.val)
        else:
            res += "#"
        if node.right:
            queue.append(node.right)
            res += str(node.right.val)
        else:
            res += "#"
    return res


def reconstruct_by_level(s: str):
    s = s.split("_")
    idx = 0
    head = genetare_node(s[idx])
    idx += 1
    queue = deque()
    queue.append(head)
    while queue:
        node = queue.popleft()
        node.left = genetare_node(s[idx])
        idx += 1
        node.right = genetare_node(s[idx])
        idx += 1
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return head


def genetare_node(s):
    if s == "#":
        return None
    return TreeNode(s)


def serialize(root):
    if not root:
        return None

    def recur(node):
        if not node:
            return "#_"
        res = str(node.val) + "_"
        res += recur(node.left)
        res += recur(node.right)

        return res

    return recur(root)


if __name__ == "__main__":

    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)

    print(serialize(head))
    # f(head)
    # print()
    # s = serial_by_pre(head)
    # node = reconstruct_by_pre(s)
    # f(node)
